package Test_1205;

/**
 * Created with Intellij IDEA
 * Description:
 * User: 星辰
 */
public class Sort {
    //直接插入排序
    public static void insetSort(int[] array){
        for (int i = 0; i < array.length; i++) {
            int tmp=array[i];
            int j=i-1;
            for (; j >=0 ;j--) {
                //如果j下标元素大于i下标位置的元素，减j下标的元素给i下标
                if(array[j]>tmp){
                    array[j+1]=array[j];
                }else{
                    array[j+1]=tmp;
                    break;
                }
            }
            array[j+1]=tmp;
        }

    }
    //希尔排序：
    public static void shellSort(int[] array){
        int gap=array.length;
        while(gap>1){
            gap=gap/2;
            //分组，排序
            shell(array,gap);
        }
    }
    private static void shell(int[] array,int gap){
        for (int i = gap; i < array.length; i++) {
            int tmp=array[i];
            int j=i-gap;
            for (; j >=0 ;j-=gap) {
                //如果j下标元素大于i下标位置的元素，减j下标的元素给i下标
                if(array[j]>tmp){
                    array[j+gap]=array[j];
                }else{
                    array[j+gap]=tmp;
                    break;
                }
            }
            array[j+gap]=tmp;
        }
    }
    //选择排序：
    public static void selectSort1(int[] array){
        int left=0;
        int right=array.length-1;
        while(left<right){
            int min=left;
            int max=left;
            for (int i = left+1; i <=right ; i++) {
                if(array[i]<array[max]){
                    max=i;
                }
                if(array[i]>array[min]){
                    min=i;
                }
            }
            swap(array,left,min);
            swap(array,right,max);
            left++;
            right++;
        }
    }
    private static void swap(int[] array,int i ,int j){
        int tmp=array[i];
        array[i]=array[j];
        array[j]=tmp;

    }
    public static void selectSort2(int[] array){
        for (int i = 0; i < array.length; i++) {
            int min=i;
            for (int j=i+1; j < array.length; j++) {
                if(array[min]>array[j]){
                    min=j;
                }
            }
            swap(array,min,i);
        }
    }
    //冒泡排序：
    public static void bubbleSort(int[] array){
        for (int i = 0; i < array.length-1; i++) {
            //有序
            boolean flg=false;
            for (int j = i; j < array.length-i-1; j++) {
                if(array[j]>array[j+1]){
                    swap(array,j,j+1);
                    //无序
                    flg=true;
                }
            }
            if(!flg){
                break;
            }
        }
    }
    //快速排序：
    //1.hoare
    public static void quickSort(int[] array){
        quick(array,0,array.length-1);
    }
    private static void quick(int[] array,int start,int end){
        if(start<end){
            return;
        }
        int pivot=partitionHoare(array,start,end);
        //递归左边
        quick(array,start,pivot-1);
        //递归右边
        quick(array,pivot+1,end);
    }
    private static int partitionHoare(int[] array,int left,int right){
        int tmp=array[left];
        int tmpleft=left;
        while(left<right){
            while(left<right && array[right]>=tmp){
                right--;
            }
            while(left<right && array[left]<=tmp){
                left++;
            }
            swap(array,left,right);
        }
        swap(array,left,tmpleft);
        return left;
    }
    //挖坑法：
    private static int partition(int[] array,int left,int right){
        int tmp=array[left];
        int tmpleft=left;
        while(left<right){
            while(left<right && array[right]>=tmp){
                right--;
            }
            array[left]=array[right];
            while(left<right && array[left]<=tmp){
                left++;
            }
            array[right]=array[left];
        }
        array[left]=tmp;
        return left;
    }
    //指针法：
    //
}
